#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int countPaths(int n, vector<vector<int>>& roads) {
	const int INF = 0x3f3f3f3f;
	vector<vector<int>> graph(n, vector<int>(n, INF));
	for (auto& v : roads)
	{
		graph[v[0]][v[1]] = v[2];
	}
	vector<int> dis(n, INF);
	dis[0] = 0;
	vector<bool> used(n);
	vector<int> dp(n);
	dp[0] = 1;
	const int MOD = pow(10, 9) + 7;
	for (int i = 0; i < n; i++)
	{
		int x = -1;
		for (int j = 0; j < n; j++)
		{
			if (!used[j] && (x == -1 || dis[j] < dis[x]))
				x = j;
		}
		used[x] = true;
		for (int j = 0; j < n; j++)
		{
			if (dis[j] > dis[x] + graph[x][j])
			{
				dis[j] = dis[x] + graph[x][j];
				dp[j] = dp[x];
			}
			else if (dis[j] == dis[x] + graph[x][j])
				dp[j] = (dp[j] + dp[x]) % MOD;
		}
	}
	return dp[n - 1];
}
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
	long long t = target[0] << 32 | target[1];
	unordered_map<long long, int> dis = { {start[0] << 32 | start[1],0},{t,INT_MAX} };
	unordered_set<long long> visited;
	while (1)
	{
		long long x = -1, dx = -1;
		for (auto& [node, distance] : dis)
		{
			if (!visited.count(node) && (x == -1 || dx < distance))
			{
				x = node;
				dx = distance;
			}
		}
		if (x == t)
			return dx;
		visited.insert(x);
		int x1 = x >> 32, x2 = x & UINT32_MAX;
		dis[t] = min(dis[t], abs(target[0] - x1) + abs(target[1] - x2) + dis[x]);
		for (auto& v : specialRoads)
		{
			int d = abs(v[0] - x1) + abs(v[1] - x2) + dis[x]+ v[4];
			long long n = (long long)(v[2] << 32) | v[3];
			if (!visited.count(n) || d < dis[n])
				dis[n] = d;
		}
	}
}
int main()
{

	return 0;
}